	/*
	 * p3632.cpp
	 *
	 *  Created on: 2013-7-19
	 *      Author: zy
	 */
	#include<cstdio>
	#include<cstring>
	#include<cmath>
	#include<iostream>
	#include<string>
	#include<vector>
	#include<set>
	#include<map>
	#include<stack>
	#include<queue>
	#include<algorithm>
	using namespace std;
	int n, a[110], d[110][110];
	bool f[110][110];
	bool check(int i, int j, int k)
	{
		return d[i][k] || d[j][k];
	}
	int main()
	{
		int T;
		scanf("%d", &T);
		for (int cas = 1; cas <= T; cas++)
		{
			scanf("%d", &n);
			for (int i = 1; i <= n; i++)
				scanf("%d", &a[i]);
			memset(f, 0, sizeof(f));
			int ans = 0;
			for (int i = 1; i <= n; i++)
				for (int j = 1; j <= n; j++)
					scanf("%d", &d[i][j]);
			for (int i = 0; i <= n + 1; i++)
			{
				d[0][i] = d[n + 1][i] = 0;
				d[i][0] = d[i][n + 1] = 1;
			}
			for (int i = 0; i <= n + 1; i++)
				f[i][i] = d[i][i] = f[i][i + 1] = 1;
			for (int i = n; i >= 0; i--)
				for (int j = i + 2; j <= n + 1; j++)
					for (int k = i + 1; k < j; k++)
						if (f[i][k] && f[k][j] && check(i, j, k))
							f[i][j] = 1;
			for (int i = 1; i <= n; i++)
				if (f[0][i] && f[i][n + 1])
					ans = max(ans, a[i]);

			printf("Case %d: %d\n", cas, ans);
		}
		return 0;
	}
